package com.hdu.other.dp.maxSubArraySum;

/**
 * link : <a href="https://leetcode.cn/problems/max-submatrix-lcci/">...</a>
 */
public class lcMaxSubMatrix {
    class Solution
    {
        public int[] getMaxMatrix(int[][] matrix)
        {

            int maxR1 = 0;
            int maxR2 = 0;
            int maxC1 = 0;
            int maxC2 = 0;
            int totalSum = Integer.MIN_VALUE;

            int m = matrix.length;
            int n = matrix[0].length;

            for (int r1 = 0; r1 < m; r1++)
            {
                int[] arr = new int[n];
                for (int r2 = r1; r2 < m; r2++)
                {
                    for (int i = 0; i < n; i++)
                    {
                        arr[i] += matrix[r2][i];
                    }
                    int preSum = Integer.MIN_VALUE;
                    int c1 = 0;
                    for (int c2 = 0; c2 < n; c2++)
                    {
                        if (preSum < 0)
                        {
                            preSum = arr[c2];
                            c1 = c2;
                        }
                        else
                        {
                            preSum += arr[c2];
                        }
                        if (preSum > totalSum)
                        {
                            totalSum = preSum;
                            maxR1 = r1;
                            maxR2 = r2;
                            maxC1 = c1;
                            maxC2 = c2;
                        }
                    }
                }
            }
            return new int[]{maxR1, maxC1, maxR2, maxC2};
        }
    }
}
